//
//  51.构建乘积数组.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/31.
//

import Foundation
/*
 题目：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
     对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
 思路1：直接用公式，暴力法O(n^2)
 思路2：分别缓存左边乘积和右边的乘积
 */
func offer_51() {
    print(Solution().multiply2([1,2,3,4,5]))
}

fileprivate class Solution {
    func multiply1(_ A: [Int]) -> [Int] {
        guard A.count > 1 else { return [] }
        var res = [Int]()
        for i in 0..<A.count {
            var arr = A
            arr.remove(at: i)
            res.append(arr.reduce(1) { $0 * $1 })
        }
        return res
    }
    
    func multiply2(_ A: [Int]) -> [Int] {
        guard A.count > 1 else { return [] }
        var res = [Int](repeating: 1, count: A.count)
        for i in 1..<A.count {
            res[i] = res[i-1] * A[i-1]
        }
        var temp = 1
        for i in (0..<A.count-1).reversed() {
            temp *= A[i+1]
            res[i] *= temp
        }
        return res
    }
}

